On Synthesizing a Consistent Operational Transformation Approach
Identifieur interne : 000639 ( Main/Exploration ); précédent : 000638; suivant : 000640On Synthesizing a Consistent Operational Transformation Approach
Auteurs : Aurel Randolph [Canada] ; Hanifa Boucheneb [Canada] ; Abdessamad Imine [France] ; Alejandro Quintero [Canada]Source :
- IEEE Transactions on Computers [ 0018-9340 ] ; 2015-02-02.
English descriptors
- mix :
Abstract
The Operational Transformation (OT) approach, used in many collaborative editors, allows a group of users to concurrently update replicas of a shared object and exchange their updates in any order. The basic idea is to transform any received update operation before its execution on a replica of the object. Concretely, OT consists of a centralized / decentralized integration procedure and a transformation function. In the context of decentralized integration, designing transformation functions for achieving convergence of object replicas is a critical and challenging issue. Indeed, the transformation functions proposed in the literature are all revealed inefficient. In this paper, we investigate the existence of transformation functions. From the theoretical point of view, two properties, named TP1 and TP2, are necessary and sufficient to ensure convergence. Using controller synthesis technique, we show that there are some transformation functions, which satisfy TP1 for the basic signatures of insert and delete operations. But, there is no transformation function, which satisfies both TP1 and TP2. Consequently, a transformation function which satisfies both TP1 and TP2 must necessarily have additional parameters in the signatures of some update operations. We propose, in this paper, a new transformation {function} and show formally that it ensures convergence.
Url:
Affiliations:
- Canada, France
- Franche-Comté, Grand Est, Lorraine (région)
- Belfort, Besançon, Metz, Nancy
- Université de Bourgogne Franche-Comté, Université de Franche-Comté, Université de Lorraine, Université de technologie de Belfort-Montbéliard
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 003707
- to stream Hal, to step Curation: 003707
- to stream Hal, to step Checkpoint: 000621
- to stream Main, to step Merge: 000639
- to stream Main, to step Curation: 000639
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On Synthesizing a Consistent Operational Transformation Approach</title><author><name sortKey="Randolph, Aurel" sort="Randolph, Aurel" uniqKey="Randolph A" first="Aurel" last="Randolph">Aurel Randolph</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-129670" status="VALID"><orgName>Laboratoire VeriForm - Department of Computer Engineering</orgName><orgName type="acronym">VeriForm</orgName><desc><address><addrLine>P.O. Box 6079, Station Centre-ville, Montr´eal, Qu´ebec,Canada, H3C 3A7</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc><listRelation><relation active="#struct-57241" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-57241" type="direct"><org type="institution" xml:id="struct-57241" status="VALID"><orgName>Ecole Polytechnique de Montreal</orgName><orgName type="acronym">EPM</orgName><desc><address><addrLine>Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Boucheneb, Hanifa" sort="Boucheneb, Hanifa" uniqKey="Boucheneb H" first="Hanifa" last="Boucheneb">Hanifa Boucheneb</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-129670" status="VALID"><orgName>Laboratoire VeriForm - Department of Computer Engineering</orgName><orgName type="acronym">VeriForm</orgName><desc><address><addrLine>P.O. Box 6079, Station Centre-ville, Montr´eal, Qu´ebec,Canada, H3C 3A7</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc><listRelation><relation active="#struct-57241" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-57241" type="direct"><org type="institution" xml:id="struct-57241" status="VALID"><orgName>Ecole Polytechnique de Montreal</orgName><orgName type="acronym">EPM</orgName><desc><address><addrLine>Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Imine, Abdessamad" sort="Imine, Abdessamad" uniqKey="Imine A" first="Abdessamad" last="Imine">Abdessamad Imine</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-189789" status="VALID"><idno type="RNSR">200318302K</idno><orgName>Combination of approaches to the security of infinite states systems</orgName><orgName type="acronym">CASSIS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/cassis</ref></desc><listRelation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-866" type="direct"></relation><relation active="#struct-242365" type="indirect"></relation><relation active="#struct-300261" type="indirect"></relation><relation active="#struct-300360" type="indirect"></relation><relation name="UMR6174" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-866" type="direct"><org type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno><idno type="RNSR">200412232H</idno><orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName><orgName type="acronym">FEMTO-ST</orgName><desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine><country key="FR"></country></address><ref type="url">http://www.femto-st.fr</ref></desc><listRelation><relation active="#struct-242365" type="direct"></relation><relation active="#struct-300261" type="direct"></relation><relation active="#struct-300360" type="direct"></relation><relation name="UMR6174" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-242365" type="indirect"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno><idno type="ISNI">0000 0001 2188 3779 </idno><orgName>Université de Franche-Comté</orgName><orgName type="acronym">UFC</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.univ-fcomte.fr</ref></desc></org></tutelle><tutelle active="#struct-300261" type="indirect"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName><orgName type="acronym">UTBM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300360" type="indirect"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName><orgName type="acronym">ENSMM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR6174" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName><placeName><settlement type="city" wicri:auto="siege">Besançon</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de Franche-Comté</orgName><orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName><placeName><settlement type="city" wicri:auto="siege">Belfort</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de technologie de Belfort-Montbéliard</orgName></affiliation></author><author><name sortKey="Quintero, Alejandro" sort="Quintero, Alejandro" uniqKey="Quintero A" first="Alejandro" last="Quintero">Alejandro Quintero</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-129670" status="VALID"><orgName>Laboratoire VeriForm - Department of Computer Engineering</orgName><orgName type="acronym">VeriForm</orgName><desc><address><addrLine>P.O. Box 6079, Station Centre-ville, Montr´eal, Qu´ebec,Canada, H3C 3A7</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc><listRelation><relation active="#struct-57241" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-57241" type="direct"><org type="institution" xml:id="struct-57241" status="VALID"><orgName>Ecole Polytechnique de Montreal</orgName><orgName type="acronym">EPM</orgName><desc><address><addrLine>Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-01094030</idno><idno type="halId">hal-01094030</idno><idno type="halUri">https://hal.archives-ouvertes.fr/hal-01094030</idno><idno type="url">https://hal.archives-ouvertes.fr/hal-01094030</idno><date when="2015-02-02">2015-02-02</date><idno type="wicri:Area/Hal/Corpus">003707</idno><idno type="wicri:Area/Hal/Curation">003707</idno><idno type="wicri:Area/Hal/Checkpoint">000621</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000621</idno><idno type="wicri:doubleKey">0018-9340:2015:Randolph A:on:synthesizing:a</idno><idno type="wicri:Area/Main/Merge">000639</idno><idno type="wicri:Area/Main/Curation">000639</idno><idno type="wicri:Area/Main/Exploration">000639</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">On Synthesizing a Consistent Operational Transformation Approach</title><author><name sortKey="Randolph, Aurel" sort="Randolph, Aurel" uniqKey="Randolph A" first="Aurel" last="Randolph">Aurel Randolph</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-129670" status="VALID"><orgName>Laboratoire VeriForm - Department of Computer Engineering</orgName><orgName type="acronym">VeriForm</orgName><desc><address><addrLine>P.O. Box 6079, Station Centre-ville, Montr´eal, Qu´ebec,Canada, H3C 3A7</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc><listRelation><relation active="#struct-57241" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-57241" type="direct"><org type="institution" xml:id="struct-57241" status="VALID"><orgName>Ecole Polytechnique de Montreal</orgName><orgName type="acronym">EPM</orgName><desc><address><addrLine>Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Boucheneb, Hanifa" sort="Boucheneb, Hanifa" uniqKey="Boucheneb H" first="Hanifa" last="Boucheneb">Hanifa Boucheneb</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-129670" status="VALID"><orgName>Laboratoire VeriForm - Department of Computer Engineering</orgName><orgName type="acronym">VeriForm</orgName><desc><address><addrLine>P.O. Box 6079, Station Centre-ville, Montr´eal, Qu´ebec,Canada, H3C 3A7</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc><listRelation><relation active="#struct-57241" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-57241" type="direct"><org type="institution" xml:id="struct-57241" status="VALID"><orgName>Ecole Polytechnique de Montreal</orgName><orgName type="acronym">EPM</orgName><desc><address><addrLine>Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Imine, Abdessamad" sort="Imine, Abdessamad" uniqKey="Imine A" first="Abdessamad" last="Imine">Abdessamad Imine</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-189789" status="VALID"><idno type="RNSR">200318302K</idno><orgName>Combination of approaches to the security of infinite states systems</orgName><orgName type="acronym">CASSIS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/cassis</ref></desc><listRelation><relation active="#struct-423084" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-866" type="direct"></relation><relation active="#struct-242365" type="indirect"></relation><relation active="#struct-300261" type="indirect"></relation><relation active="#struct-300360" type="indirect"></relation><relation name="UMR6174" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423084" type="direct"><org type="department" xml:id="struct-423084" status="VALID"><orgName>Department of Formal Methods </orgName><orgName type="acronym">LORIA - FM</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/formal-methods</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-866" type="direct"><org type="laboratory" xml:id="struct-866" status="VALID"><idno type="IdRef">152639071</idno><idno type="RNSR">200412232H</idno><orgName>Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies</orgName><orgName type="acronym">FEMTO-ST</orgName><desc><address><addrLine>32 avenue de l'Observatoire 25044 BESANCON CEDEX</addrLine><country key="FR"></country></address><ref type="url">http://www.femto-st.fr</ref></desc><listRelation><relation active="#struct-242365" type="direct"></relation><relation active="#struct-300261" type="direct"></relation><relation active="#struct-300360" type="direct"></relation><relation name="UMR6174" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-242365" type="indirect"><org type="institution" xml:id="struct-242365" status="VALID"><idno type="IdRef">026403188</idno><idno type="ISNI">0000 0001 2188 3779 </idno><orgName>Université de Franche-Comté</orgName><orgName type="acronym">UFC</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.univ-fcomte.fr</ref></desc></org></tutelle><tutelle active="#struct-300261" type="indirect"><org type="institution" xml:id="struct-300261" status="VALID"><orgName>Université de Technologie de Belfort-Montbeliard</orgName><orgName type="acronym">UTBM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300360" type="indirect"><org type="institution" xml:id="struct-300360" status="VALID"><orgName>Ecole Nationale Supérieure de Mécanique et des Microtechniques</orgName><orgName type="acronym">ENSMM</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="UMR6174" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName><placeName><settlement type="city" wicri:auto="siege">Besançon</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de Franche-Comté</orgName><orgName type="institution" wicri:auto="newGroup">Université de Bourgogne Franche-Comté</orgName><placeName><settlement type="city" wicri:auto="siege">Belfort</settlement><region type="region" nuts="2">Franche-Comté</region></placeName><orgName type="university">Université de technologie de Belfort-Montbéliard</orgName></affiliation></author><author><name sortKey="Quintero, Alejandro" sort="Quintero, Alejandro" uniqKey="Quintero A" first="Alejandro" last="Quintero">Alejandro Quintero</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-129670" status="VALID"><orgName>Laboratoire VeriForm - Department of Computer Engineering</orgName><orgName type="acronym">VeriForm</orgName><desc><address><addrLine>P.O. Box 6079, Station Centre-ville, Montr´eal, Qu´ebec,Canada, H3C 3A7</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc><listRelation><relation active="#struct-57241" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-57241" type="direct"><org type="institution" xml:id="struct-57241" status="VALID"><orgName>Ecole Polytechnique de Montreal</orgName><orgName type="acronym">EPM</orgName><desc><address><addrLine>Campus de l'Université de Montréal 2500, chemin de Polytechnique Montréal (Québec) H3T 1J4</addrLine><country key="CA"></country></address><ref type="url">http://www.polymtl.ca/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></analytic><series><title level="j">IEEE Transactions on Computers</title><idno type="ISSN">0018-9340</idno><imprint><date type="datePub">2015-02-02</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Collaborative editors</term><term>controller synthesis</term><term>operational transformation</term><term>proof of convergence</term><term>symbolic model checking</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The Operational Transformation (OT) approach, used in many collaborative editors, allows a group of users to concurrently update replicas of a shared object and exchange their updates in any order. The basic idea is to transform any received update operation before its execution on a replica of the object. Concretely, OT consists of a centralized / decentralized integration procedure and a transformation function. In the context of decentralized integration, designing transformation functions for achieving convergence of object replicas is a critical and challenging issue. Indeed, the transformation functions proposed in the literature are all revealed inefficient. In this paper, we investigate the existence of transformation functions. From the theoretical point of view, two properties, named TP1 and TP2, are necessary and sufficient to ensure convergence. Using controller synthesis technique, we show that there are some transformation functions, which satisfy TP1 for the basic signatures of insert and delete operations. But, there is no transformation function, which satisfies both TP1 and TP2. Consequently, a transformation function which satisfies both TP1 and TP2 must necessarily have additional parameters in the signatures of some update operations. We propose, in this paper, a new transformation {function} and show formally that it ensures convergence.</div></front></TEI><affiliations><list><country><li>Canada</li><li>France</li></country><region><li>Franche-Comté</li><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Belfort</li><li>Besançon</li><li>Metz</li><li>Nancy</li></settlement><orgName><li>Université de Bourgogne Franche-Comté</li><li>Université de Franche-Comté</li><li>Université de Lorraine</li><li>Université de technologie de Belfort-Montbéliard</li></orgName></list><tree><country name="Canada"><noRegion><name sortKey="Randolph, Aurel" sort="Randolph, Aurel" uniqKey="Randolph A" first="Aurel" last="Randolph">Aurel Randolph</name></noRegion><name sortKey="Boucheneb, Hanifa" sort="Boucheneb, Hanifa" uniqKey="Boucheneb H" first="Hanifa" last="Boucheneb">Hanifa Boucheneb</name><name sortKey="Quintero, Alejandro" sort="Quintero, Alejandro" uniqKey="Quintero A" first="Alejandro" last="Quintero">Alejandro Quintero</name></country><country name="France"><region name="Grand Est"><name sortKey="Imine, Abdessamad" sort="Imine, Abdessamad" uniqKey="Imine A" first="Abdessamad" last="Imine">Abdessamad Imine</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000639 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000639 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Hal:hal-01094030
|texte= On Synthesizing a Consistent Operational Transformation Approach
}}
| This area was generated with Dilib version V0.6.33. |  |